<!DOCTYPE html>
<!--[if lt IE 7 ]><html class="ie ie6" lang="en"> <![endif]-->
<!--[if IE 7 ]><html class="ie ie7" lang="en"> <![endif]-->
<!--[if IE 8 ]><html class="ie ie8" lang="en"> <![endif]-->
<!--[if (gte IE 9)|!(IE)]><!-->
<html lang="en">
<!--<![endif]-->

<head>

    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="description" content="">
    <meta name="author" content="">
    <meta name="keywords" content="">

    <title>Bankers Algorithm</title>

    {% load static %}
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/fonts/font-awesome-4.3.0/css/font-awesome.min.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/stroke.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/bootstrap.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/animate.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/prettyPhoto.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/style.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/js/syntax-highlighter/styles/shCore.css' %}" media="all">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/js/syntax-highlighter/styles/shThemeRDark.css' %}" media="all">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/custom.css' %}">

    <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
    <!--[if lt IE 9]>
      <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
      <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
    <![endif]-->

</head>

<body>

    <div id="wrapper">

        <div class="container">

            <section id="top" class="section docs-heading">

                <div class="row">
                    <div class="col-md-12">
                        <div class="big-title text-center">
                            <h1>Bankers Algorithm</h1>
                        </div>
                        <!-- end title -->
                    </div>
                    <!-- end 12 -->
                </div>
                <!-- end row -->

                <hr>

            </section>
            <!-- end section -->

            <div class="row">

                <div class="col-md-3">
                    <nav class="docs-sidebar" data-spy="affix" data-offset-top="300" data-offset-bottom="200" role="navigation">
                        <ul class="nav">
                            <li><a href="#line1">Introduction</a></li>
                            <li><a href="#line2">Banker's Algorithm</a></li>
                            <li><a href="#line3">Safe State and Safe Sequence</a></li>
                            <li><a href="#line4">Data Structures used in Banker's Algorithm</a></li>
                            <li><a href="#line5">The Safety Algorithm</a></li>
                            <li><a href="#line6">Resource Request Algorithm</a></li>
                        </ul>
                    </nav >
                </div>
                <div class="col-md-9">
                    <section id = "line1" class="welcome">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Introduction<hr></h2>
                                <div class="row">

                                    <div class="col-md-12 full">
                                        <div class="intro1">
                                            <ul>
                                                <!-- <li><strong>Demo Page : </strong><a href="http://themeforest.net/user/surjithctly" target="_blank">Click Here</a></li> -->
                                                <li><strong>Front End Developers : </strong>Aneesh Aithal</li>
                                                <li><strong>Backend End Developers : </strong>Aneesh Aithal</li>
                                                <li><strong>Content : </strong>Karthik M</li>
                                            </ul>
                                        </div>

                                        <hr>
                                        <div>
                                            <p> Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages.
                                            </p>

                                            <p> When the page that was selected for replacement and was paged out, is referenced again, it has to read in from disk, and this requires for I/O completion. This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
                                            </p>

                                            <p> A page replacement algorithm looks at the limited information about accessing the pages provided by hardware, and tries to select which pages should be replaced to minimize the total number of page misses, while balancing it with the costs of primary storage and processor time of the algorithm itself. There are many different page replacement algorithms. We evaluate an algorithm by running it on a particular string of memory reference and computing the number of page faults.
                                            </p>

                                            <h4>Types</h4>
                                            <p>There are 3 major types</p>
                                            <ol>
                                                <li>First In First Out (FIFO)</li>
                                                <li>Least Recently Used (LRU)</li>
                                                <li>Optimal Page Replacement (OPR)</li>
                                            </ol>
                                        </div>
                                    </div>
                                </div>
                                <!-- end row -->
                            </div>
                        </div>
                    <hr>
                    </section>

                    <section id="line2" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Banker's Algorithm<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <p>It is a deadlock avoidance algorithm which dynamically examines the resource allocation state to ensure that a deadlock does not occur. To achieve this, a system should have a knowledge of the complete sequence of requests and releases for each process to avoid a future possible deadlock</p>
                            <!-- end col -->
                        </div>
                        <!-- end row -->
                    </section>
                    <!-- end section -->

                    <section id="line3" class="section">
                        <hr>
                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Safe State and Safe Sequence<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <p>A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence. A sequence of processes <P1, P2, ..., Pn> is a safe sequence for the current allocation state if, for each Pi, the resource requests that Pi can still make can be satisfied by the currently available resources plus the resources held by all Pj, with j <i.</p>
                            <!-- end col -->
                        </div>
                        <!-- end row -->
                        <hr>
                    </section>
                    <!-- end section -->

                    <section id="line4" class="section">

                        <div class="row">
                            <hr>
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Data Structures used in Banker’s Algorithm<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <pre>Let n be the number of processes in the system and m be the number of resource types

Available:  A vector of length m indicates the number of available resources of each type
Max:  An n × m matrix defines the maximum demand of each process
Allocation: An n × m matrix defines the number of resources of each type currently allocated to each process.
Need:  An n × m matrix indicates the remaining resource need of each process. Need[i][j] = Max[i][j] − Allocation[i][j].

We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocation[i] and Need[i]. The vector Allocation[i] specifies the resources currently allocated to process P[i]; the vector Need[i] specifies the additional resources that process P[i] may still request to complete its task.

                                </pre>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <hr>
                    </section>

                    <section id="line5" class="section">
                        <hr>
                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">The Safety Algorithm<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">

                                  <p>This algorithm can be described as follows:</p>
                                <pre>
1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.

2. Find an index i such that both
a. Finish[i] == false
b. Need[i] ≤ Work

If no such i exists, go to step 4.

3. Work = Work + Allocation[i]
Finish[i] = true
Go to step 2.

4. If Finish[i] == true for all i, then the system is in a safe state.


                                </pre>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <section id="line6" class="section">
                            <hr>
                            <div class="row">
                                <div class="col-md-12 left-align">
                                    <h2 class="dark-text">Resource Request Algorithm<a href="#top">#back to top</a><hr></h2>
                                </div>
                                <!-- end col -->
                            </div>
                            <!-- end row -->

                            <div class="row">
                                    <pre>
Let Request[i] be the request vector for process P[i]. If Request[i][j] == k, then process P[i] wants k instances of resource type R[j]. When a request for resources is made by process P[i], the following actions are taken:

1. If Request[i] ≤Need[i], go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.

2. If Request[i] ≤ Available, go to step 3. Otherwise, P[i] must wait, since the resources are not available.

3. Have the system pretend to have allocated the requested resources to process P[i] by modifying the state as follows:

Available = Available–Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] –Request[i];

If the resulting resource-allocation state is safe, the transaction is completed, and process P[i] is allocated its resources. However, if the new state is unsafe, then P[i] must wait for Request[i], and the old resource-allocation state is restored.


                                    </pre>
                                <!-- end col -->
                            </div>
                            <!-- end row -->
                            <!-- <div class = "row">
                              <h4 id ="line4_4">Example</h4>
                            </div>
                            <div class="col-md-6">
                                <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                                <h4>Input</h4>
                            </div>
                            <div class="col-md-6">
                                <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                                <h4>Output</h4>
                            </div> -->

                        <hr>
                    </section>


                      <hr>

                    <!-- end section -->
                </div>
                <!-- // end .col -->

            </div>
            <!-- // end .row -->

        </div>
        <!-- // end container -->

    </div>
    <!-- end wrapper -->

    <script src="{%static 'wikipages/js/jquery.min.js' %}"></script>
    <script src="{%static 'wikipages/js/bootstrap.min.js' %}"></script>
    <script src="{%static 'wikipages/js/retina.js' %}"></script>
    <script src="{%static 'wikipages/js/jquery.fitvids.js' %}"></script>
    <script src="{%static 'wikipages/js/wow.js' %}"></script>
    <script src="{%static 'wikipages/js/jquery.prettyPhoto.js' %}"></script>
    <script src="{%static 'wikipages/js/custom.js' %}"></script>
    <script src="{%static 'wikipages/js/main.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shCore.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushXml.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushCss.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushJScript.js' %}"></script>

</body>

</html>
